//
// Created by Administrator on 2021/5/24.
//
/*
有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印由 同一个字符 组成的序列。
每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。
给你一个字符串 s ，你的任务是计算这个打印机打印它需要的最少打印次数。
*/

#include <string>
#include <vector>
#include <iostream>

using namespace std;

class Solution {
public:
    int strangePrinter(string s) {
        /**
         * dp
         * dp[i][j]表示从i到j字符需要的最小打印次数
         * 如果s[i]==s[j] dp[i][j] = dp[i][j-1] 因为s[i] s[j]可以在同一次打印过程中得到
         * else
         *      遍历 k from i to j-1
         *      dp[i][j] = min(dp[i][k] + dp[k+1][j]
         *      O(n^3)
         */
        int n = (int) s.size();
        vector<vector<int>> dp(n, vector<int>(n, n));
        for (int i = n - 1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; ++j) {
                if (s[i] == s[j]) dp[i][j] = dp[i][j - 1];
                else {
                    for (int k = i; k < j; ++k) {
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }
        return dp[0][n - 1];
    }

    int strangePrinter2(string s) {
        if (s.empty()) return 0;
        //去除连续相同·字符
        int index = 0;
        string str;
        while (index < s.size()) {
            char ch = s[index++];
            str += ch;
            while (index < s.size() && s[index] == ch) {
                index++;
            }
        }
        int n = (int) str.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));
        for (int i = n - 1; i >= 0; --i) {
            dp[i][i] = 1;
            for (int j = i + 1; j < n; ++j) {
                if (str[i] == str[j]) dp[i][j] = dp[i][j - 1];
                else {
                    dp[i][j] = n;
                    for (int k = i; k < j; ++k) {
                        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }
        return dp[0][n - 1];
    }
};


class Solution2 {  // 优秀题解
public:
    int strangePrinter(string s) {
        if (s.empty()) return 0;
        //去除连续相同·字符
        int index = 0;
        string str;
        while (index < s.size()) {
            char ch = s[index++];
            str += ch;
            while (index < s.size() && s[index] == ch) {
                index++;
            }
        }
        int n = (int) str.size();
        //dp[i][j]表示从第i个字符到第j个字符（包括两端）需要的打印次数
        // 初始值为 -1
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, -1));
        return helper(1, n, dp, str);
    }

    int helper(int l, int r, vector<vector<int>> &dp, string &str) {
        if (dp[l][r] != -1) return dp[l][r];
        if (l > r) return dp[l][r] = 0;
        int res = helper(l, r - 1, dp, str) + 1;
        for (int m = l; m < r; ++m) {
            if (str[m - 1] == str[r - 1]) { // 和右端点相同
                // 中间可以优化的部分
                res = min(res, helper(l, m - 1, dp, str) + helper(m, r - 1, dp, str));
            }
        }
        return dp[l][r] = res;
    }
};
class Solution3 {
public:
    int strangePrinter(string s) {
        if (s.empty()) return 0;
        int n = (int)s.size();
         vector<vector<int>> dp(n, vector<int>(n, n));
        for(int i = 0; i < n; i++)
            dp[i][i] = 1;
        for(int len = 2; len <= n; len++) {
            for(int i = 0, j = len-1; j < n; i++, j++) {
                if(s[i] == s[j])
                    dp[i][j] = min(dp[i+1][j], dp[i][j-1]);
                else {
                    for(int k = i; k < j; k++)
                        dp[i][j] = min(dp[i][j], dp[i][k]+dp[k+1][j]);
                }
            }
        }
        return dp[0][n-1];
    }
};
int main() {
    Solution sol;
    Solution2 sol2;
    Solution3 sol3;
    cout << sol.strangePrinter("aaabbb") << endl;
    cout << sol.strangePrinter2("abcabc") << endl;
    cout << sol2.strangePrinter("aaabbb") << endl;
    cout << sol2.strangePrinter("abcabc") << endl;
    cout << sol3.strangePrinter("abcabc") << endl;
    return 0;
}